Diffie-Hellman key exchange, as described in U.S. Pat. No. 4,200,770, is a well known example of how two parties can exchange a cryptographic key. Diffie-Hellman key exchange is itself not a public key cryptosystem. Embodiments of the present invention, on the other hand, are public key cryptosystems. In a public key cryptosystem, two parties wishing to communicate securely, e.g., over an open network such as the Internet, each have a private key, known only to the party, and a mathematically related public key that is made publicly available. It is computationally infeasible to derive the private key from the public key. A first party wishing to communicate securely with a second party encrypts plaintext with the public key of the second party and sends the resulting ciphertext to the second party. The second party then decrypts the ciphertext with the second party's private key to retrieve the plaintext. Public key cryptography can also be used for authentication of digital documents, including over open networks.
One drawback of public key cryptography is that it is relatively slow compared with symmetric key cryptography, in which the same key is used for encryption and decryption. Therefore, public key cryptography is often used, not to encrypt the entire plaintext, but to exchange between the parties a symmetric key. The symmetric key is then used to encrypt the plaintext and decrypt the resulting ciphertext.
The Diffie-Hellman method is based on the apparent difficulty in computing logarithms over a finite field GF(q) having a prime number q of elements. For two communicating parties i and j, the Diffie-Hellman method uses a key K=aXiXj mod q, where “mod” denotes a modulo operation. Modulo is similar to the operation of obtaining a remainder in an arithmetic division. In the Diffie-Hellman method, a party i publishes in a public location the value Yi=aXi mod q, where Xi is a private undisclosed positive integer. To communicate with a party j, party i obtains a key Kij by computing Kij=(Yj)Xi mod q. Similarly, party j obtains the key Kij by computing Kij=(Yi)Xj mod q.
The Diffie-Hellman method has been widely used for the last 25 years, but the existence of a subexponential algorithm (called the index calculus), which can attack Diffie-Hellman, forces Diffie-Hellman users to employ longer key sizes in order to stay secure against increasing computing powers. Hence, it is desirable to have a key exchange algorithm for which an index calculus or similar attack algorithm doesn't exist. The present invention, which uses subsets with certain commuting property, solves this problem.